/*
 * @Author: your name
 * @Date: 2020-09-09 10:17:56
 * @LastEditTime: 2020-09-09 10:29:16
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /MergeSort/MergeSort.cpp
 */
#include <iostream>
using namespace std;

// //一次二路归并排序算法如下：
// void Merge(int a[], int n, int swap[], int k)
// //k为子数组长度，一次二路归并排序后的子序列存于数组swap中
// {        
//     int m = 0, u1,l2,i,j,u2;  
//     int l1 = 0;				//第一个有序子数组下界为0
// 	while(l1+k <= n-1)
// 	{        
//         l2 = l1 + k;			//第二个有序子数组下界
// 	    u1 = l2 - 1;			//第一个有序子数组上界
// 	    u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;  //第二个子数组上界
//         //两个有序子数组合并
// 	    for(i = l1, j = l2; i <= u1 && j <= u2; m++)	
// 	    {     
// 		    if(a[i]<= a[j])
// 		    {        
//                 swap[m] = a[i];   
//                 i++;        
//             }
// 		    else
// 		    {        
//                 swap[m]=a[j];  
//                 j++;        
//             }
// 		}   
//       //子数组2已完，将子数组1中剩余的元素存放到swap
// 	    while(i <= u1)
// 	    {        
//             swap[m] = a[i];      
//             m++;        
//             i++;	
//         }
//         //子数组1已完，将子数组2中剩余的元素存放到swap
//         while(j <= u2)
// 	    {        
//             swap[m] = a[j];      
//             m++;        
//             j++;	
//         }
//         l1 = u2 + 1;
//     }
//     //将原始数组中只够一组的数据元素顺序存放到数组swap
//     for(i = l1; i < n; i++, m++)  
//     swap[m] = a[i];
// }
void merge(int a[],int l,int r,int mid)
{
    int aux[r-l+1],i,j,k;
    for(k=l;k<=r;k++)
    aux[k-l]=a[k];
    i=l;
    j=mid+1;
    for(k=l;k<=r;k++)
    {
        if(i>mid)
  	    {
  		    a[k]=aux[j-l];
  		    j++;
	    }
	    else if(j>r)
	    {
		    a[k]=aux[i-l];
		    i++;
	    }
	    else if(aux[i-l]>aux[j-l])
	    {
		    a[k]=aux[j-l];
		    j++;
	    }
	    else
	    {
		    a[k]=aux[i-l];
		    i++;
	    }
    }	
	
}
 
void merge_sort(int a[],int l,int r)
{
    if(l>=r)
	return ;
	int mid=(l+r)/2;
	merge_sort(a,l,mid);
	merge_sort(a,mid+1,r);
	merge(a,l,r,mid);	
	
}
 
 
void mergesort(int a[],int l,int r)
{
	merge_sort(a,l,r-1);
}


int main()
{
    int arry[8]={10,39,35,27,89,62,47,18};
    for (int i = 0; i<8; i++)
    {
        cout<<arry[i]<<" ";
    }
    cout<<endl;
    mergesort(arry,0,8);
    for (int i = 0; i<8; i++)
    {
        cout<<arry[i]<<" ";
    }
    cout<<endl;
    return 0;
}